package master;


/**
 * 回复二叉搜索树
 *
 * @author chenyw
 * @date 2022/7/31 11:33
 */
public class M99recoverTree {
    TreeNode cur;
    TreeNode preNode;
    TreeNode pre;
    public void recoverTree(TreeNode root) {
//        int pre = Integer.MIN_VALUE;
        TreeNode pre = new TreeNode(Integer.MIN_VALUE);
        dfs(root);
        int tmp = preNode.val;
        preNode.val = cur.val;
        cur.val = tmp;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        //中序遍历，记录逆序对的第一个节点和最后一个节点
        //逆序对可能有两个（连续的）3-2-1，可能只有一个2-1
        if (pre != null && root.val < pre.val) {
            if (preNode == null) {
                preNode = pre;
            }
            cur = root;
        }
        pre = root;

        dfs(root.right);
    }

}
